//
// Created by user on 2022/3/15.
//

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
    };
//迭代写法
ListNode* reverseList(ListNode* head) {
    if(!head||!head->next)return head;
    ListNode *prev = nullptr;
    ListNode *curr = head;

    while (curr){
        ListNode *next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

//递归写法
ListNode* reverseList1(ListNode* head) {
    if(!head || !head->next){
        return head;
    }
    ListNode *p = reverseList1(head->next);

    head->next->next = head;
    head->next = nullptr;

    return p;
}